package C059;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c02
 * Package: C059
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/8 00:31
 * @Version 1.0
 * @Since 1.0
 */
public class c02 {
    public static void main(String[] args) {
        int[][] arr = {{1,0},{2,0},{3,1},{3,2}};
        System.out.println(Arrays.toString(findOrder(4, arr)));
    }


    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            graph.add(list);
        }

        // 统计入度
        int[] indegree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }

        // 初始化拓扑队列
        int[] queue = new int[numCourses];
        int r = 0, l = 0;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }

        // 计算结果
        int count = 0;
        while(r > l) {
            // 获得队列点邻接表
            List<Integer> list = graph.get(queue[l++]);
            for (int i = 0; i < list.size(); i++) {
                if(-- indegree[list.get(i)] == 0) {
                    queue[r++] = list.get(i);
                }
            }
            count ++;
        }

        return count == numCourses ? queue : new int[0];
    }
}
